<html>
<head><meta charset="utf-8"><title>type_id analysis · t-compiler/wg-polymorphization · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/index.html">t-compiler/wg-polymorphization</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html">type_id analysis</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="211410139"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410139" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410139">(Sep 27 2020 at 10:42)</a>:</h4>
<p>So one of the bigger issues we have is <code>type_id</code> and <code>type_name</code>. As <code>type_name</code> has neither stable nor unique output, I don't think we have to care about that and can "just" print polymorphized types. One issue here would be that identical types could have different outputs (if they are polymorphized in one case but not in another, but that also seems fine to me)</p>



<a name="211410167"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410167" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410167">(Sep 27 2020 at 10:44)</a>:</h4>
<p>One of the solutions for <code>type_id</code> which has already been talked about would be to analyse where types are used in <code>type_id</code> and not polymorphize these instances</p>



<a name="211410210"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410210" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410210">(Sep 27 2020 at 10:44)</a>:</h4>
<p>this has some issues with incremental compilation and perf though as it requires a query accessing all optimized mirs of a crate</p>



<a name="211410269"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410269" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410269">(Sep 27 2020 at 10:46)</a>:</h4>
<p>So I guess my idea would be to test adding two queries.</p>
<p><code>crate_polymorphize_restrictions</code>: a global analysis which is not cached on disk and needs the mir of all bodies</p>



<a name="211410285"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410285" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410285">(Sep 27 2020 at 10:47)</a>:</h4>
<p>this query creates a <code>FxHashMap&lt;DefId, BitSet&lt;u32&gt;&gt;</code> indicating which generic parameters of the instance with <code>DefId</code> may be polymorphized</p>



<a name="211410324"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410324" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410324">(Sep 27 2020 at 10:48)</a>:</h4>
<p><code>polymorphize_restrictions_of</code>: a cached query which simply uses <code>tcx.crate_polymorphize_restrictions(def_id)</code> and is the one actually used during collection to check if a given instance may be polymorphized</p>



<a name="211410377"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410377" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410377">(Sep 27 2020 at 10:49)</a>:</h4>
<p>I think <code>crate_polymorphize_restrictions</code> should be fairly fast to compute so I hope it isn't a big perf issue that we compute it at every incremental run. This would be similar to what <code>crate_variances</code> does atm</p>



<a name="211410382"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410382" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410382">(Sep 27 2020 at 10:49)</a>:</h4>
<p>cc <span class="user-mention" data-user-id="116107">@davidtwco</span> <span class="user-mention" data-user-id="119009">@eddyb</span> does this idea seem worth trying?</p>



<a name="211410486"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410486" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410486">(Sep 27 2020 at 10:51)</a>:</h4>
<p><span class="user-mention silent" data-user-id="216206">lcnr</span> <a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/211410167">said</a>:</p>
<blockquote>
<p>One of the solutions for <code>type_id</code> which has already been recommended by some people would be to analyse where types are used in <code>type_id</code> and not polymorphize these instances</p>
</blockquote>
<p>If you consider the type parameter of <code>type_id</code> as used that will prevent polymorphization of it, right?</p>



<a name="211410612"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410612" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410612">(Sep 27 2020 at 10:54)</a>:</h4>
<p>the issue is more complex</p>



<a name="211410620"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410620" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410620">(Sep 27 2020 at 10:54)</a>:</h4>
<p>let me get an example</p>



<a name="211410628"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410628" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410628">(Sep 27 2020 at 10:54)</a>:</h4>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">nop</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span><span class="p">{}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">test_the_waters</span><span class="o">&lt;</span><span class="n">A</span>: <span class="o">'</span><span class="nb">static</span><span class="p">,</span><span class="w"> </span><span class="n">B</span>: <span class="o">'</span><span class="nb">static</span><span class="o">&gt;</span><span class="p">(</span><span class="n">a</span>: <span class="nc">A</span><span class="p">,</span><span class="w"> </span><span class="n">_</span>: <span class="nc">B</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="kd">let</span><span class="w"> </span><span class="n">any</span>: <span class="nb">Box</span><span class="o">&lt;</span><span class="k">dyn</span><span class="w"> </span><span class="n">std</span>::<span class="n">any</span>::<span class="n">Any</span><span class="o">&gt;</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nb">Box</span>::<span class="n">new</span><span class="p">(</span><span class="n">a</span><span class="p">);</span><span class="w"></span>
<span class="w">    </span><span class="n">assert</span><span class="o">!</span><span class="p">(</span><span class="n">any</span><span class="p">.</span><span class="n">downcast_ref</span>::<span class="o">&lt;</span><span class="n">A</span><span class="o">&gt;</span><span class="p">().</span><span class="n">is_some</span><span class="p">());</span><span class="w"></span>
<span class="w">    </span><span class="n">assert</span><span class="o">!</span><span class="p">(</span><span class="n">any</span><span class="p">.</span><span class="n">downcast_ref</span>::<span class="o">&lt;</span><span class="n">B</span><span class="o">&gt;</span><span class="p">().</span><span class="n">is_none</span><span class="p">());</span><span class="w"></span>
<span class="w">    </span><span class="n">assert</span><span class="o">!</span><span class="p">(</span><span class="n">any</span><span class="p">.</span><span class="n">downcast_ref</span>::<span class="o">&lt;</span><span class="k">fn</span><span class="p">()</span><span class="o">&gt;</span><span class="p">().</span><span class="n">is_none</span><span class="p">());</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">main</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">test_the_waters</span><span class="p">(</span><span class="n">nop</span>::<span class="o">&lt;</span><span class="kt">u32</span><span class="o">&gt;</span><span class="p">,</span><span class="w"> </span><span class="n">nop</span>::<span class="o">&lt;</span><span class="kt">u64</span><span class="o">&gt;</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="211410632"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410632" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410632">(Sep 27 2020 at 10:54)</a>:</h4>
<p><a href="https://github.com/rust-lang/rust/issues/75325">#75325</a></p>



<a name="211410650"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410650" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410650">(Sep 27 2020 at 10:55)</a>:</h4>
<p>So  <code>nop</code> doesn't use <code>T</code> here so we can polymorphize <code>nop::&lt;u32&gt;</code> and <code>nop::&lt;u64&gt;</code> to an identical type</p>



<a name="211410795"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410795" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410795">(Sep 27 2020 at 10:58)</a>:</h4>
<p><a href="https://github.com/davidtwco/rust/blob/ac50d61785ae5112b9b4e30a58cfcffe096b31ec/src/test/codegen-units/polymorphization/pr-75255.rs">https://github.com/davidtwco/rust/blob/ac50d61785ae5112b9b4e30a58cfcffe096b31ec/src/test/codegen-units/polymorphization/pr-75255.rs</a></p>
<p>this polymorphization allows us to only create one instance of <code>iter::repeat</code> in</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">fn</span> <span class="nf">unused</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span>-&gt; <span class="kt">u64</span> <span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="mi">42</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">bar</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">std</span>::<span class="n">iter</span>::<span class="n">repeat</span><span class="p">(</span><span class="n">unused</span>::<span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">);</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>


<span class="k">pub</span><span class="w"> </span><span class="k">fn</span> <span class="nf">dispatch</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">bar</span>::<span class="o">&lt;</span><span class="nb">String</span><span class="o">&gt;</span><span class="p">();</span><span class="w"></span>
<span class="w">    </span><span class="n">bar</span>::<span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="nb">String</span><span class="o">&gt;&gt;</span><span class="p">();</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="211410817"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410817" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410817">(Sep 27 2020 at 10:59)</a>:</h4>
<p>but the issue is that <code>repeat</code> does use its type parameter and can observe the polymorphization of <code>unused</code> with <code>type_id</code></p>



<a name="211410864"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410864" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410864">(Sep 27 2020 at 11:00)</a>:</h4>
<p>I didn't think about that.</p>



<a name="211410869"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211410869" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211410869">(Sep 27 2020 at 11:00)</a>:</h4>
<p>so did we <span aria-label="laughter tears" class="emoji emoji-1f602" role="img" title="laughter tears">:laughter_tears:</span></p>



<a name="211411097"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411097" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411097">(Sep 27 2020 at 11:07)</a>:</h4>
<p>Is there a case where this is actually a problem or is it only to preserve the semantics of TypeId? Because in the first example having <code>nop&lt;i32&gt; == nop&lt;i64&gt;</code> would seem pretty logical to me. </p>
<p>One could argue that you could break code  that relies on TypeId just by starting to use <code>T</code> inside <code>nop</code> but we already have the same thing happening with closures, where the type is automatically derived, too</p>



<a name="211411114"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411114" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411114">(Sep 27 2020 at 11:07)</a>:</h4>
<p><a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/211410628">https://rust-lang.zulipchat.com/#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/211410628</a></p>
<p>this is unsound</p>



<a name="211411130"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411130" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411130">(Sep 27 2020 at 11:08)</a>:</h4>
<p>there is a more realistic example, let me find it</p>



<a name="211411192"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411192" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411192">(Sep 27 2020 at 11:09)</a>:</h4>
<p><a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/TypeId.20guarantees/near/206290008">https://rust-lang.zulipchat.com/#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/TypeId.20guarantees/near/206290008</a></p>



<a name="211411264"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411264" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411264">(Sep 27 2020 at 11:11)</a>:</h4>
<blockquote>
<p>but we already have the same thing happening with closures</p>
</blockquote>
<p>what do you mean here? if you mean in relation to polymorphization, then that's also unsound and something the above idea would fix</p>



<a name="211411429"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411429" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411429">(Sep 27 2020 at 11:15)</a>:</h4>
<p>I was only talking about the fact that closure can change its type when you change the code inside it, which is not the case for normal functions today</p>



<a name="211411486"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411486" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> panstromek <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411486">(Sep 27 2020 at 11:16)</a>:</h4>
<p>I didn't realize the unsoundness, I thought its only about guarantees of TypeId</p>



<a name="211411507"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411507" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411507">(Sep 27 2020 at 11:17)</a>:</h4>
<p>well, the unsoundness stems from the guarantees of <code>TypeId</code></p>



<a name="211411696"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211411696" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211411696">(Sep 27 2020 at 11:22)</a>:</h4>
<p>There used to be a <code>Reflect</code> trait that was necessary to use <code>TypeId</code>. I think it was removed as there is no referential transparency in rust anyway. It would have been really nice in this case if it still existed. All you would have to do is to check for a <code>Reflect</code> bound and prevent polymorphization of said type parameter.</p>



<a name="211413665"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413665" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413665">(Sep 27 2020 at 12:13)</a>:</h4>
<p>I’m open to trying your proposed approach.</p>



<a name="211413749"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413749" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413749">(Sep 27 2020 at 12:15)</a>:</h4>
<p>If I’m not mistaken, we could polymorphize more with a global analysis like this (e.g. <code>foo</code> calls <code>bar</code> with <code>T</code> and <code>bar</code> doesn’t use it, so we can polymorphize both).</p>



<a name="211413879"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413879" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413879">(Sep 27 2020 at 12:18)</a>:</h4>
<p>hmm yeah, I guess we can't use a bitset in this case though</p>



<a name="211413885"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413885" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413885">(Sep 27 2020 at 12:19)</a>:</h4>
<p>as  there are at least three different states here</p>



<a name="211413890"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413890" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413890">(Sep 27 2020 at 12:19)</a>:</h4>
<p>A global analysis will play very bad with incremental compilation. Especially when you have cycles (see for example the MIR inliner)</p>



<a name="211413944"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413944" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413944">(Sep 27 2020 at 12:20)</a>:</h4>
<p>We have</p>
<ul>
<li>unused params: <code>fn noop&lt;T&gt;() {]</code></li>
<li>used params which may contain polymorphized types: <code>std::iterator::map</code></li>
<li>used params which may not contain polymorphized types: <code>TypeId::of</code></li>
</ul>



<a name="211413951"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413951" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413951">(Sep 27 2020 at 12:21)</a>:</h4>
<p>So cheap global analysis are sometimes fine from what I have seen</p>



<a name="211413954"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211413954" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211413954">(Sep 27 2020 at 12:21)</a>:</h4>
<p>we already do this pattern to compute variances</p>



<a name="211414004"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414004" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414004">(Sep 27 2020 at 12:22)</a>:</h4>
<p>And by using a cached query to get the data for a given <code>DefId</code> we don't break the incremental cache</p>



<a name="211414009"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414009" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414009">(Sep 27 2020 at 12:22)</a>:</h4>
<p>so the only added cost of the global analysis is recomputing <code>crate_polymorphization_restrictions</code> every time</p>



<a name="211414037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> bjorn3 <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414037">(Sep 27 2020 at 12:23)</a>:</h4>
<p>That could easily cause a chain effect where changing a single function would end up effecting a lot of other functions.</p>



<a name="211414088"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414088" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414088">(Sep 27 2020 at 12:24)</a>:</h4>
<p>Yeah, the query has to be fairly stable here which is the case for subtrees which use <code>TypeId</code></p>



<a name="211414115"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414115" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414115">(Sep 27 2020 at 12:25)</a>:</h4>
<p>I might be underestimating how often we add or remove subtrees which depend on <code>TypeId::of</code></p>



<a name="211414133"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414133" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414133">(Sep 27 2020 at 12:26)</a>:</h4>
<p>but I expect polymorphizability(words?) to be fairly stable between compilations</p>



<a name="211414173"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414173" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414173">(Sep 27 2020 at 12:26)</a>:</h4>
<p>unlike the total amount of reachable functions</p>



<a name="211414186"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211414186" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211414186">(Sep 27 2020 at 12:26)</a>:</h4>
<p>which depends quite heavily on the content of all called functions</p>



<a name="211415174"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/211415174" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#211415174">(Sep 27 2020 at 12:50)</a>:</h4>
<p>Either way, it’s working giving it a shot and seeing what perf we get - I’m not aware of any other options for solving our issue with <code>TypeId</code>.</p>



<a name="222183291"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183291" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183291">(Jan 09 2021 at 18:40)</a>:</h4>
<p>so i've kept thinking about this and don't think that the global analysis would actually be cheap here as it has to be both quite pessimistic in case an instance is still too generic and won't allow us to nested calls</p>



<a name="222183421"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183421" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183421">(Jan 09 2021 at 18:43)</a>:</h4>
<p>afaict we can get away with polymorphizing closures even when used in other types as we don't guarantee that closures inherit their parent generics</p>



<a name="222183435"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183435" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183435">(Jan 09 2021 at 18:43)</a>:</h4>
<p>so only polymorphizing closures is probably something we can "just" do</p>



<a name="222183502"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183502" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183502">(Jan 09 2021 at 18:44)</a>:</h4>
<p><span class="user-mention" data-user-id="116107">@davidtwco</span> did you and <span class="user-mention silent" data-user-id="119009">eddyb</span> consider polymorphizing lazily during mono item collection?</p>



<a name="222183632"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183632" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183632">(Jan 09 2021 at 18:47)</a>:</h4>
<p>By polymorphizing lazily, would that be equivalent to only polymorphizing at the last moment? e.g. instead of all mono items in the set being polymorphized or none; mono items remain unchanged but at certain key locations in codegen, we polymorphize (such as generating the symbol name for a function)?</p>



<a name="222183684"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183684" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183684">(Jan 09 2021 at 18:48)</a>:</h4>
<p>my idea was something like this but i didn't look too deeply into this yet:</p>



<a name="222183709"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183709" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183709">(Jan 09 2021 at 18:49)</a>:</h4>
<p>afaict mono item collection starts at concrete roots and then recursively adds all concrete instances which are needed by these concrete items</p>



<a name="222183739"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183739" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183739">(Jan 09 2021 at 18:50)</a>:</h4>
<p><span class="user-mention silent" data-user-id="216206">lcnr</span> <a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/222183709">said</a>:</p>
<blockquote>
<p>afaict mono item collection starts at concrete roots and then recursively adds all concrete instances which are needed by these concrete items</p>
</blockquote>
<p>that's my understanding too</p>



<a name="222183845"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183845" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183845">(Jan 09 2021 at 18:52)</a>:</h4>
<p>my idea would be to change <code>unused_generic_params</code> to be optimistic</p>



<a name="222183863"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183863" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183863">(Jan 09 2021 at 18:53)</a>:</h4>
<p>so only consider a param <em>used</em> if it's used by the <code>type_id</code> intrinsic, required for layout or anything else I am missing</p>



<a name="222183933"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183933" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183933">(Jan 09 2021 at 18:54)</a>:</h4>
<p>so for <code>foo&lt;T&gt;() { bar::&lt;T&gt;() }</code>, <code>foo</code> would not consider <code>T</code> <em>used</em> (probably better to call it something like required, idk)</p>



<a name="222183953"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183953" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183953">(Jan 09 2021 at 18:55)</a>:</h4>
<p>so now, when looking at <code>foo::&lt;i32&gt;</code> during collection</p>



<a name="222183962"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222183962" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222183962">(Jan 09 2021 at 18:55)</a>:</h4>
<p>we see that it requires <code>bar::&lt;T/i32&gt;</code></p>



<a name="222184011"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184011" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184011">(Jan 09 2021 at 18:56)</a>:</h4>
<p>and if <code>bar</code> does not recursively use <code>T</code> we can polymorphize <code>foo</code></p>



<a name="222184099"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184099" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184099">(Jan 09 2021 at 18:58)</a>:</h4>
<p>if <code>bar&lt;i32&gt;</code> were to again depend on <code>foo&lt;i32&gt;</code> we can start by just considering <code>i32</code> used here</p>



<a name="222184123"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184123" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184123">(Jan 09 2021 at 18:59)</a>:</h4>
<p>but there are probably a lot of clever ways to allow for partial polymorphization here <span aria-label="shrug" class="emoji emoji-1f937" role="img" title="shrug">:shrug:</span></p>



<a name="222184282"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184282" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184282">(Jan 09 2021 at 19:02)</a>:</h4>
<p>I'm struggling to make concrete in my head what that would look like - it would still require some way of knowing whether <code>bar</code> would depend on <code>foo</code> (alternatively: that <code>foo</code> is recursive) which we can't determine in the query, right? And that's why we'd try to keep track of the "possibilities for polymorphization" (whether we will end up with <code>T</code> or <code>i32</code>) outside of that, in the collector?</p>
<p>I've been meaning to look into <span class="user-mention silent" data-user-id="124288">oli</span>'s work on preventing query cycles in the MIR inliner to see if the technique could be applied here.</p>



<a name="222184316"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184316" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184316">(Jan 09 2021 at 19:03)</a>:</h4>
<p>As an aside, I want to land some tests for the type id problem that we've observed, because I vaguely remember expecting some tests that we'd written in the past to fail and having them succeed with polymorphization - so wanted to confirm that, with the current implementation, it is in fact broken in ways that we expect (I can't remember exactly when that was, since it's been a while since I was actively working on polymorphization - I'll be re-focusing my attention on this effort in the next week or two).</p>



<a name="222184340"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184340" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184340">(Jan 09 2021 at 19:03)</a>:</h4>
<p>mono item collection isn't a query so recursive dependencies aren't too bad i think</p>



<a name="222184403"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184403" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184403">(Jan 09 2021 at 19:04)</a>:</h4>
<p><span class="user-mention silent" data-user-id="216206">lcnr</span> <a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/222184340">said</a>:</p>
<blockquote>
<p>mono item collection isn't a query so recursive dependencies aren't too bad i think</p>
</blockquote>
<p>yeah, we absolutely could do that in the collector - I just wanted to clarify that the "during collection" part was the key difference that avoided the current cycle error issue</p>



<a name="222184412"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184412" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184412">(Jan 09 2021 at 19:04)</a>:</h4>
<p>yeah, so we move checking dependencies into the mono item collector</p>



<a name="222184506"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184506" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184506">(Jan 09 2021 at 19:07)</a>:</h4>
<p>Utilizing <code>mir_callgraph_reachable</code> from <a href="https://github.com/rust-lang/rust/issues/68828">#68828</a> might be an interesting approach if that lands, as (if I'm understanding it correctly) we'd be able to just use that within the <code>unused_generic_params</code> query and we'd be able to leverage those results already being computed by the inliner (if it were enabled).</p>



<a name="222184563"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184563" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184563">(Jan 09 2021 at 19:08)</a>:</h4>
<p>i think that won't work as <code>mir_callgraph_reachable</code> has different requirements</p>



<a name="222184571"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184571" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184571">(Jan 09 2021 at 19:08)</a>:</h4>
<p>I haven't looked at <a href="https://github.com/rust-lang/rust/issues/68828">#68828</a> closely, so that might be the case.</p>



<a name="222184583"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184583" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184583">(Jan 09 2021 at 19:09)</a>:</h4>
<p>not sure how it currently works but afaik it "ignores" unresolved instances</p>



<a name="222184671"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184671" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184671">(Jan 09 2021 at 19:11)</a>:</h4>
<p>so something like</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">trait</span><span class="w"> </span><span class="n">Bar</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="k">fn</span> <span class="nf">hey</span><span class="p">()</span><span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="k">impl</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="n">Bar</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">     </span><span class="k">fn</span> <span class="nf">hey</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">        </span><span class="n">type_of</span>::<span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">();</span><span class="w"></span>
<span class="w">    </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">foo</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">bar</span>::<span class="o">&lt;</span><span class="nb">Vec</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;&gt;</span><span class="p">();</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>

<span class="k">fn</span> <span class="nf">bar</span><span class="o">&lt;</span><span class="n">T</span>: <span class="nc">Bar</span><span class="o">&gt;</span><span class="p">()</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">    </span><span class="n">Bar</span>::<span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span>::<span class="n">hey</span><span class="p">();</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>



<a name="222184720"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184720" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184720">(Jan 09 2021 at 19:12)</a>:</h4>
<p>cc <span class="user-mention" data-user-id="124288">@oli</span> <a href="https://github.com/rust-lang/rust/issues/68828">#68828</a> considers <code>bar</code> to not call <code>type_of</code> here i think</p>



<a name="222184725"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184725" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184725">(Jan 09 2021 at 19:12)</a>:</h4>
<p>When first implementating polymorphization, there was some circumstance that meant that we thought cycle errors were inevitable with polymorphization (I can't remember what it was now). While we thought about how to work around that, I had a very hacky diff that inspected the query stack and just looked for a previous <code>unused_generic_params</code> query with the same key, and if that was the case, returned "used" for the parameter in question. That the parameter was "used" would eventually percolate back up to the previous invocation that we observed.</p>



<a name="222184762"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222184762" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222184762">(Jan 09 2021 at 19:13)</a>:</h4>
<p>ah, I see, that makes sense</p>



<a name="222277780"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222277780" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222277780">(Jan 11 2021 at 10:01)</a>:</h4>
<p><span class="user-mention silent" data-user-id="216206">lcnr</span> <a href="#narrow/stream/216091-t-compiler.2Fwg-polymorphization/topic/type_id.20analysis/near/222184720">said</a>:</p>
<blockquote>
<p>cc <span class="user-mention silent" data-user-id="124288">oli</span> <a href="https://github.com/rust-lang/rust/issues/68828">#68828</a> considers <code>bar</code> to not call <code>type_of</code> here i think</p>
</blockquote>
<p>right, only <code>foo</code> calls <code>type_of</code></p>



<a name="222307345"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222307345" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lcnr <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222307345">(Jan 11 2021 at 15:01)</a>:</h4>
<blockquote>
<p>I'll be re-focusing my attention on this effort in the next week or two</p>
</blockquote>
<p><span class="user-mention" data-user-id="116107">@davidtwco</span> do you want to experiment with my idea? Otherwise I am going to take a few days this month to try this myself</p>



<a name="222307391"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222307391" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222307391">(Jan 11 2021 at 15:01)</a>:</h4>
<p>Feel free to, there's some other things I'll look at first.</p>



<a name="222318078"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/216091-t-compiler/wg-polymorphization/topic/type_id%20analysis/near/222318078" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/216091-t-compiler/wg-polymorphization/topic/type_id.20analysis.html#222318078">(Jan 11 2021 at 16:11)</a>:</h4>
<p>note that you can compute the full "possible call graph" on top of the one that I computed, and it should be fairly cheap I think?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>